\chapter{Introduction}

Similarity measurement processes are a core part of most machine learning algorithms. Traditional approaches focus on either taxonomic (``A and B share properties x, y and z'') or thematic (``A is similar to B by value N'') thinking. Psychological research, e.g.\cite{wisniewski1999makes}, suggests that a combination of both is needed to adequately model human-like similarity perception. 

Any model combining those aspects is called a Similarity Dual Process Model.  Even though other, unrelated dual processes exist in research, we refer to our Similarity Dual Process Model as DPM for the rest of this work.

The primary aim of this thesis is to provide an implementation of the DPM idea. It should perform binary classification and be adoptable to carry out other machine learning tasks like, for example, cluster analysis, correlation and ranking. The most important question for the implementation is: How can we smoothly integrate a DPM into machine learning algorithms?

The secondary aim of this work is to test DPMs in real-world experiments. The selected scenario should have intermediate applications, while still being simple enough to generate results within reasonable time. The experimental setup should be justified - i.e. it should be clear why which decision was made. In addition, the experiments should be easily reproducible for others. 

The question for the experimental results is: Which DPMs performed best? While answering this question, we have to rule out the possibility that our best DPMs are just a product of coincidence and a search space with too many degrees of freedom.

\begin{figure}[ph!]
	\centering
	\includegraphics[scale=0.3]{triad.png}
	\caption{Taxonomic and Thematic Thinking (cf. \cite[p. 540]{eidenberger2012handbook})}
	\label{fig:triad}
\end{figure}

Figure \ref{fig:triad} tries to develop an intuitive understanding with an example. The triangle on the left side is the reference. We compare it to the two objects next to it. If the focus lies on taxonomic thinking, the triangle in the center is more similar to the reference, because it also has three corners. If the focus lies on thematic thinking, the square on the right is less different from the reference, because it has a smaller height difference.

At first sight, the combination of both concepts seems an unnecessary complication. After all, both have been used on their own in machine learning - mainly in models created by computer scientists. Humans, however, do not always use one or the other approach when making similarity judgments.

One experiment asked participants to rate the similarity of word pairs on a numeric scale, e.g. (milk, coffee), (milk, lemonade), (milk, cow) and (milk, horse). ``\textit{As one would expect, similarity ratings for pairs which were highly alignable were reliably higher than for pairs which were poorly alignable.  However, contrary to present accounts of similarity, ratings for pairs with preexisting thematic relations were higher than for pairs without preexisting thematic relation.}'' \cite[p.~216--217]{wisniewski1999makes}

In other words, humans tend to think that a cow is more similar to  milk than a horse is to milk, because the associate a cow with giving milk. If machine learning is used to solve a purely  ``objective'' task, for example predicting the number of newspapers to ship to a certain town, then this finding might be irrelevant. If the task is to model human behavior, for example recognizing pedestrians in images, then this finding (and others related to taxonomic and thematic thinking) is highly relevant.

We now have most ingredients for formulating a DPM. One remaining complication is that not all humans use taxonomic and thematic to the same extent. During the rest of this thesis, this issue is dealt with by using an importance of taxonomic thinking factor. The calibration of this factor can be done on a per-person basis with psychological tests.    

\begin{equation}
\label{formula:simple-dpm}
s_{dpm} = \alpha\  s_{taxonomic} + (1-\alpha)\ g(d_{thematic})
\end{equation}

Equation \ref{formula:simple-dpm} shows a simple DPM \cite[p. 540]{eidenberger2012handbook} with the following parts:

\begin{itemize}

\item Similarity $s_{dpm}$
\item Importance of taxonomic thinking $\alpha, 0 \leq \alpha \leq 1$
\item Specific taxonomic measure $s_{taxonomic}$ 
\item Specific generalization function $g$ (for converting distance to similarity)
\item Specific thematic measure $d_{thematic}$

\end{itemize}

The specific taxonomic measure, thematic measure and generalization function to be plugged into the equation are the reader's decision. Section \ref{sec:perf} lists some good options which were found during experimentation. Note that, for the rest of this work, we deal with linear combinations of taxonomic and thematic thinking only. Apart from keeping things simple, there is no other rationale behind this choice. It is entirely possible that, for example, a cubic DPM poses a better choice.

We close this introduction with an overview of the chapters to come. Chapter \ref{chp:background} introduces the reader to the concepts we need later on. This chapter also plays the role of a brief literature survey. DPMs are a novel approach to measuring similarity. Therefore, we discuss other models for measuring similarity that have been proposed. Next, we further explain taxonomic and thematic thinking and two different kinds of measures.

Afterwards, we turn to more technical aspects arising from the real-world task we selected: the detection of pedestrians in images. It was selected, because of its interesting applications (e.g. automatic braking for pedestrians in modern cars, computer games with a new level of interactivity and many more) and because various well-known algorithms already exist for it. 

For pedestrian detection, we make use of the image detection algorithm Histogram of Oriented Gradients and two other algorithms from the MPEG-7 standard:  Scalable Color Descriptor and Edge Histogram Descriptor. A discussion of Support Vector Machines, which are binary classifiers, concludes the chapter.

Chapter \ref{chp:imp} describes how we reached our primary goal. After an overview, we discuss the implementation of pedestrian detection. Next, we turn to the implementation of measures, generalization functions and DPM kernels. The complete code is provided as a free download. The last part of this chapter is a discussion of the experimental setup. 

We go through the outcomes of the experiments in Chapter \ref{chp:results}. We start with a comparison to existing models and discuss the viability of DPMs. Next, we take a look at the effect of using different generalization functions and different measures. At this point, we are able to list the DPMs that performed best, thereby reaching our secondary goal. Evidence for the statistical significance of the results concludes the chapter.

Eventually, Chapter \ref{chp:summary} gives a conclusion and mentions promising areas of further research.
